
/**
 * @Project : Clion_ProgrammingExercises
 * @File : 0128
 * @Author : WangRuoyu 
 * @Date : 2023/5/24 15:06
 */

#include "iostream"
#include "vector"
#include "algorithm"
#include <unordered_set>

using namespace std;

// O(n) O(n)
class Solution {
public:
    int longestConsecutive(vector<int> &nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        unordered_set<int> used;

        int res = 0;
        for (int a: set) {
            if (used.count(a)) continue;
            int tmp = 1;
            for (int i = a + 1;; ++i) {
                if (!set.count(i)) break;
                used.insert(i);
                tmp++;
            }
            for (int i = a - 1;; --i) {
                if (!set.count(i)) break;
                used.insert(i);
                tmp++;
            }
            res = max(res, tmp);
        }
        return res;
    }
};

// O(nlogn) O(1)
//class Solution {
//public:
//    int longestConsecutive(vector<int> &nums) {
//        if (nums.empty()) {
//            return 0;
//        }
//        sort(nums.begin(), nums.end());
//        int res = 1;
//        int cur = 1;
//        for (int i = 0; i < nums.size() - 1; ++i) {
//            if (nums[i + 1] == nums[i] + 1) {
//                cur++;
//                res = max(res, cur);
//            } else if (nums[i] == nums[i + 1]) {
//                continue;
//            } else {
//                cur = 1;
//            }
//        }
//        return res;
//    }
//};

int main() {
    Solution sl;
    vector<int> nums = {5};
    printf("%d", sl.longestConsecutive(nums));
    return 0;
}